4. Linked Lists

Linked Lists

$O(n)$ access but $O(1)$ append and pop!

Fast and Slow

This is usually the easiest way to get to the "middle" of a linked list in $O(n)$ time (since fast would have traversed the entire thing)

Pseudocode:

resp = ListNode()
resp.next = head
fast = resp
slow = resp

while fast.next and fast.next.next:
    slow = slow.next
    fast = fast.next.next

# At this point slow.next is the middle
do_something_here(slow.next)

return(resp.next)

There's an example of Deleting The Middle Node Of A Linked List that does just this!

Reversal

Reversing a Linked List involves using temporary node holders and then just swapping prev and next values along the way

# create an eventual response, which will point to resp.next (which would be tail!)
resp = ListNode(0, head)
curr = head
prev = resp

# 1 --> 2 --> 3
# curr = 1
# prev = resp() --> 1
while curr:
    # 2
    next_node = curr.next
    
    # resp <-- 1 
    # 2 --> 3
    curr.next = prev

    # prev = 1
    # curr = 2
    prev = curr
    curr = next_node

# This would return head of new, reversed, LinkedList
return(prev)

# This would return tail 
return(resp.next)

Skip Lists

Skip lists are a probabilistic data structure that utilize Linked Lists - at each further level down more nodes are "revealed", and it more and more looks like a tree the more you stare at it

Level 4: HEAD --------------------------------> [100] -> NULL
Level 3: HEAD --------> [20] ---------------> [100] -> NULL
Level 2: HEAD -> [10] -> [20] -> [50] -------> [100] -> NULL
Level 1: HEAD -> [10] -> [20] -> [30] -> [50] -> [100] -> NULL

Each node in a skip list contains:

• A score (float64)
• A member string
• Forward pointers for each level
• A backward pointer (for reverse iteration)
• A span (number of nodes skipped at each level)

Each level's forward pointer tracks the span (nodes skipped). This allows ranking operations like ZRANK in Redis ZSets to compute rank in O(log N) by summing spans